package cn.leonis.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Author Tobi
 * @Date 2021-07-10 上午12:30
 * 最大子数组,Return Sum
 */
public class MaximumSubarraySolution {

    public static void main(String[] args) {
        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        MaximumSubarraySolution solution = new MaximumSubarraySolution();
        System.out.println(solution.maxSubArray(nums));
    }

    public int maxSubArray(int[] nums) {
        int pre = 0, maxSub = nums[0];
        for (int num: nums) {
            pre = Math.max(pre + num, num);
            maxSub = Math.max(maxSub, pre);
        }
        return maxSub;
    }
}
